package hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Lc105 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        int nodeVal = preorder[0];
        int nodeIdxInOrder = indexOf(inorder, nodeVal);
        int[] inLeft = Arrays.copyOfRange(inorder, 0, nodeIdxInOrder);
        int[] inRight = Arrays.copyOfRange(inorder, nodeIdxInOrder + 1, inorder.length);
        int[] preLeft = Arrays.copyOfRange(preorder, 1, 1 + inLeft.length);
        int[] preRight = Arrays.copyOfRange(preorder, 1 + inLeft.length, preorder.length);
        return new TreeNode(nodeVal, buildTree(preLeft, inLeft), buildTree(preRight, inRight));
    }

    private int indexOf(int[] arr, int val) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == val) {
                return i;
            }
        }
        return 0;
    }
}
